class Solution(object):
    def strobogrammaticInRange(self, low, high):
        """
        :type low: str
        :type high: str
        :rtype: int
        """
        d = {'0': 0, '1': 1, '2': 2, '3': 2, '4': 2, '5': 2, '6': 2, '7': 3, '8': 3, '9': 4}
        d2 = {'0': 0, '1': 1, '2': 2, '3': 2, '4': 2, '5': 2, '6': 2, '7': 3, '8': 2, '9': 3}
        match_dict = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}

        @functools.lru_cache(maxsize=None)
        def search(k, n):
            if k <= 1:
                if k == 1:
                    return 3
                else:
                    return 1
            else:
                if k == 2:
                    if k < n:
                        return 5
                    else:
                        return 4
                else:
                    if k == n:
                        return 4 * search(k - 2, n)
                    else:
                        return 5 * search(k - 2, n)

        # not include s
        def find_top_to(s):
            n = len(s)
            already = 0
            k = 0
            flag = True
            while k < n // 2:
                if k == 0:
                    already += (d[s[k]] - 1) * search(n - 2 * k - 2, n)
                else:
                    already += d[s[k]] * search(n - 2 * k - 2, n)
                if s[k] not in ['0', '1', '6', '8', '9']:
                    flag = False
                    break
                if k == n // 2 - 1:
                    if n % 2 == 0:
                        t = s[: k + 1]
                        for m in range(k, -1, -1):
                            t += match_dict[s[m]]
                        if t < s:
                            already += 1
                    else:
                        t = s[: k + 2]
                        for m in range(k, -1, -1):
                            t += match_dict[s[m]]
                        if t < s:
                            already += 1
                k += 1
            if flag and n % 2 == 1:
                already += d2[s[k]]
            return already

        def judge(s):
            n = len(s)
            for i in range(n // 2):
                if s[i] not in match_dict:
                    return False
                if s[i] in match_dict and s[n - 1 - i] != match_dict[s[i]]:
                    return False
            if n % 2 == 1:
                if s[n // 2] not in ['0', '1', '8']:
                    return False
            return True

        num1 = find_top_to(high)
        for i in range(len(low), len(high)):
            num1 += search(i, i)
        num2 = find_top_to(low)
        return num1 - num2 + judge(high)